/*
 * @lc app=leetcode.cn id=279 lang=golang
 *
 * [279] 完全平方数
 */

// @lc code=start

func numSquares(n int) int {
	if n <= 1 {
		return n
	}
	dp := make([]int, n+1)
	dp[1] = 1
	dp[2] = 2
	for i := 3; i < n+1; i++ {
		t := n + 1
		for j := 1; j*j <= i; j++ {
			t = min(t, dp[i-j*j]+1)
		}
		dp[i] = t
	}
	return dp[n]
}

func min(i, j int) int {
	if i < j {
		return i
	}
	return j
}

// @lc code=end
